package _17_剑指Offer;

import _01_动态数组._剑指_Offer41数据流中的中位数;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class _41_剑指Offer数据流中的中位数 {

    public static void main(String[] args) {
        _41_剑指Offer数据流中的中位数 v = new _41_剑指Offer数据流中的中位数();
        v.addNum(2);
        v.addNum(3);
        v.addNum(4);
        System.out.println(v.findMedian());
    }

    // 存放较小元素，但是它是大顶堆
    private final Queue<Integer> maxQueue;

    // 存放较大元素，但它是小顶堆
    private final Queue<Integer> minQueue;

    public _41_剑指Offer数据流中的中位数() {
        maxQueue = new PriorityQueue<>((a1, a2) -> a2 - a1);
        minQueue = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxQueue.size() == minQueue.size()) {
            minQueue.add(num);
            maxQueue.add(minQueue.poll());
        } else {
            maxQueue.add(num);
            minQueue.add(maxQueue.poll());
        }
    }

    public double findMedian() {
        return maxQueue.size() == minQueue.size()? (maxQueue.peek() + minQueue.peek()) / 2.0: maxQueue.peek();
    }

    private List<Integer> containers = new ArrayList<>();

    public void addNum1(int num) {
        // 搜索插入位置
        containers.add(binarySearch(num), num);
    }

    public double findMedian1() {
        // 奇，偶数
        int size = containers.size();
        int mid = size >> 1;
        double value;
        if ((size & 1) == 0) {
            value = (containers.get(mid) + containers.get(mid - 1)) / 2.0;
        } else {
            value = containers.get(mid);
        }
        return value;
    }

    private int binarySearch(int value) {
        // 找到第一个大于等于的数
        int left = 0;
        int results = containers.size();
        int right = results - 1;
        while (left <= right) {
            int mid = left + right >> 1;
            if (containers.get(mid) >= value) {
                results = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return results;
    }
}
